/*
题目: 美观的花束
力扣嘉年华的花店中从左至右摆放了一排鲜花，记录于整型一维矩阵 flowers 中每个数字表示该位置所种鲜花的品种编号。你可以选择一段区间的鲜花做成插花，且不能丢弃。
在你选择的插花中，如果每一品种的鲜花数量都不超过 cnt 朵，那么我们认为这束插花是 「美观的」。
 */
public class BeautifulBouquet {
    private static final int mod = (int) 1e9 + 7;
    public int beautifulBouquet(int[] flowers, int cnt) {
        // 滑动窗口, 子数组问题
        Map<Integer, Integer> map = new HashMap<> ();
        int n = flowers.length;

        int src = 0, left = 0;
        for (int i = 0; i < n; i ++) {
            map.put(flowers[i], map.getOrDefault(flowers[i], 0) + 1);

            while (map.get(flowers[i]) > cnt) {
                map.put(flowers[left], map.get(flowers[left]) - 1);
                left ++;
            }
            src += i - left + 1;
            src %= mod;
        }

        return src;
    }
}
